package 剑指offer.数组;

/**
 * 此题较为特殊，重复出现的数字只有两次（偶数次）
 * 假设只有一个数字只出现一次，如：1, 2, 2, 2, 2, 3, 3, 3, 3
 * 用 ^ 运算可在 O(n) 的时间内找到只出现一次的数字，具体做法就是：
 * int[] array = new int[]{1, 2, 2, 2, 2, 3, 3, 3, 3};
 * int a = 0;
 * for (int i = 0; i < array.length; i++) {
 * a = a ^ array[i];
 * }
 * a 就是只出现一次的数字
 * <p>
 * 但是现在是找两个只出现一次的数字
 * 可以把数组划分成两部分A、B，每一部分里面只有一个数字只出现一次，这样就把问题转换成上面的形式了
 * <p>
 * 现在的问题是如何划分数组：
 * 还是遍历一遍数组并执行异或运算，最后的结果一定是这两个单一数字的^结果（可自己写份示例代码验证），如：
 * int[] array = new int[]{1, 2, 2, 4, 3, 3};
 * int a = 0;
 * for (int i = 0; i < array.length; i++) {
 * a = a ^ array[i];
 * }
 * System.out.println(a);     // 5
 * System.out.println(1 ^ 4); // 5
 * <p>
 * 在这个例子中 5 的二进制是 0101
 */
public class 第56题数组中只出现一次的数字 {

    /**
     * @param array
     * @param num1  num1, num2分别为长度为 1 的数组。传出参数
     * @param num2  将 num1[0], num2[0]设置为返回结果
     */
    public static void FindNumsAppearOnce(int[] array, int num1[], int num2[]) {
        int a = 0;
        for (int i = 0; i < array.length; i++) {
            a = a ^ array[i];
        }
        // 从右边开始，找到二进制中第一个 1 的位数 index
        /*
        以第n位是不是1为标准把元数组中的数字分成两个子数组，
            第一个子数组中每个数字的第n位都是1，而第二个子数组中每个数字的第n位都是0。

        举例：{2,4,3,6,3,2,5,5}

        我们依次对数组中的每个数字做异或运行之后，得到的结果用二进制表示是 0010。
        异或得到结果中的倒数第二位是1，于是我们根据数字的倒数第二位是不是1分为两个子数组。
        第一个子数组{2,3,6,3,2}中所有数字的倒数第二位都是1，而第二个子数组{4,5,5}中所有数字的倒数第二位都是 0。
        接下来只要分别两个子数组求异或，就能找到第一个子数组中只出现一次的数字是6，而第二个子数组中只出现一次的数字是
         */
        int index = indexForFirst1(a);

        // 遍历每一个数，判断它的第index位是不是1，来划分数组
        // 针对每一部分数组，再次执行 ^ 即可得到该部分数组里面的单一数字
        int ans1 = 0;
        int ans2 = 0;
        for (int i = 0; i < array.length; i++) {
            if (is1InIndexN(array[i], index)) {
                // 第一部分数组
                ans1 = ans1 ^ array[i];
            } else {
                // 第二部分数组
                ans2 = ans2 ^ array[i];
            }
        }
        num1[0] = ans1;
        num2[0] = ans2;
    }

    // 找到二进制中第一个 1 出现的位数
    public static int indexForFirst1(int number) {
        int index = 1;
        while ((number & 1) == 0) {
            number = number >> 1;
            index++;
        }
        return index;
    }

    // 判断该数的第 n 位是否为 1（输入的n是第一个1的index）
    public static boolean is1InIndexN(int number, int index) {
        return ((number >> (index - 1)) & 1) == 1 ? true : false;
    }

    public static void main(String[] args) {

        int[] array = {1, 2, 2, 3, 4, 4};
        int[] nums1 = new int[1];
        int[] nums2 = new int[1];
        FindNumsAppearOnce(array, nums1, nums2);
        System.out.println(nums1[0]);
        System.out.println(nums2[0]);

    }
}
